#include <iostream>
using namespace std;
#include <vector>
#include <string.h>
#include <functional>

namespace zq
{
    template <class T>
    struct less
    {
        bool operator()(const T & e1, const T & e2)
        {
            return e1 < e2;
        }
    };

    template <class T>
    struct greater
    {
        bool operator()(const T & e1, const T & e2)
        {
            return e1 > e2;
        }
    };

    // 这里的less表示大堆
    template <class T, class Container = vector<T>, class Compare = less<T>>
    class priority_queue
    {
    public:
        void swap(int &e1, int &e2)
        {
            int tmp = e1;
            e1 = e2;
            e2 = tmp;
        }
        void AdjustUp(int child)
        {
            Compare compare;
            int parent = (child - 1) / 2;
            while (child > 0)
            {
                if (compare(_con[parent], _con[child]))
                {
                    swap(_con[child], _con[parent]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }
        void AdjustDown(int root)
        {
            Compare compare;
            int parent = root;
            int child = 2 * parent + 1;
            // 找出左右孩子中最大的那个
            while (child < _con.size())
            {
                if (child + 1 < _con.size() && compare(_con[child], _con[child + 1]))
                {
                    ++child;
                }

                if (compare(_con[parent], _con[child]))
                {
                    swap(_con[child], _con[parent]);
                    parent = child;
                    child = 2 * parent + 1;
                }
                else
                {
                    break;
                }
            }
        }
        void push(const T &x)
        {
            _con.push_back(x);
            AdjustUp(_con.size() - 1);
        }

        void pop()
        {
            // 和最后一个元素交换
            swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();
            AdjustDown(0); // 再进行向下调整算法
        }

        T &top()
        {
            return _con[0];
        }
        size_t size()
        {
            return _con.size();
        }
        bool empty()
        {
            return _con.empty();
        }

    private:
        Container _con;
    };

    void test1()
    {
        priority_queue<int,vector<int>,greater<int>> pq;
        pq.push(1);
        pq.push(3);
        pq.push(2);
        pq.push(6);

        while (!pq.empty())
        {
            cout << pq.top() << " ";
            pq.pop();
        }
        cout << endl;
    }

}